package everydayone.message;
/**
 * @Date 2020/03/23
 * @author 王光浩
 * @Thinking 使用备忘录（将空间复杂度优化成O（n））
 * @Analysis 时间复杂度O（n），空间复杂度O（n）
 */
public class MyMethodFive {
	public int massage(int[] nums) {
		if(nums.length==0)return 0;
		if(nums.length==1)return nums[1];
		if(nums.length==2)return Math.max(nums[0], nums[1]);
		int[] dp=new int[nums.length];
		dp[nums.length-1]=nums[nums.length-1];
		dp[nums.length-2]=Math.max(nums[nums.length-2],nums[nums.length-1]);
		for(int i=nums.length-3;i>=0;i--)
			dp[i]=Math.max(nums[i]+dp[i+2], dp[i+1]);
		return dp[0];
	}	
}
